package MemorySearch;
/**
 * P509 斐波那契数列
 * */
public class P509 {
    public static void main(String[] args) {
        P509Test01 p509Test01=new P509Test01();

        System.out.println(p509Test01.fib(5));
    }
}
/*
* 解法一：递归
* */
class P509Test01{

    //记忆化搜索，利用数组来存储结构，避免子问题结果重合
    private int[] fx;
    public int fib(int n) {
        fx=new int[n+5];
        fx[0]=0;
        fx[1]=1;
        return f(n);
    }
    private int f(int n){
        if(n==0)
            return fx[0];
        if(n==1)
            return fx[1];

        if(fx[n]!=0){
            return fx[n];
        }
        fx[n]=f(n-1)+f(n-2);
        return fx[n];
    }
}
/*
* 解法二：循环
* */

class P509Test02{
    public int fib(int n) {
        int[] f=new int[n+1];
        f[0]=0;
        f[1]=1;

        for(int i=2;i<=n;i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}